{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Nodes From Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #recursion #linked-list #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #递归 #链表 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从链表中移除节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个链表的头节点 <code>head</code> 。</p>\n",
    "\n",
    "<p>移除每个右侧有一个更大数值的节点。</p>\n",
    "\n",
    "<p>返回修改后链表的头节点<em> </em><code>head</code><em> </em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/02/drawio.png\" style=\"width: 631px; height: 51px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [5,2,13,3,8]\n",
    "<strong>输出：</strong>[13,8]\n",
    "<strong>解释：</strong>需要移除的节点是 5 ，2 和 3 。\n",
    "- 节点 13 在节点 5 右侧。\n",
    "- 节点 13 在节点 2 右侧。\n",
    "- 节点 8 在节点 3 右侧。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,1,1,1]\n",
    "<strong>输出：</strong>[1,1,1,1]\n",
    "<strong>解释：</strong>每个节点的值都是 1 ，所以没有需要移除的节点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>给定列表中的节点数目在范围 <code>[1, 10<sup>5</sup>]</code> 内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-nodes-from-linked-list](https://leetcode.cn/problems/remove-nodes-from-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-nodes-from-linked-list](https://leetcode.cn/problems/remove-nodes-from-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,2,13,3,8]', '[1,1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 无脑做法\n",
    "        l = []\n",
    "        while head:\n",
    "            l.append(head)\n",
    "            head = head.next\n",
    "        \n",
    "        head = None\n",
    "        mx = 0\n",
    "        for node in l[::-1]:\n",
    "            if node.val >= mx:\n",
    "                mx = node.val\n",
    "                node.next = head\n",
    "                head = node\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 无脑做法\n",
    "        l = []\n",
    "        while head:\n",
    "            l.append(head)\n",
    "            head = head.next\n",
    "        \n",
    "        head = None\n",
    "        mx = 0\n",
    "        for node in l[::-1]:\n",
    "            if node.val >= mx:\n",
    "                mx = node.val\n",
    "                node.next = head\n",
    "                head = node\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        nodes_array = []\n",
    "        mono_stack = []\n",
    "        i = 0\n",
    "        while head:\n",
    "            nodes_array.append(head)\n",
    "            while mono_stack and head.val > nodes_array[mono_stack[-1]].val:\n",
    "                mono_stack.pop(-1)\n",
    "            mono_stack.append(i)\n",
    "            i += 1\n",
    "            head = head.next\n",
    "        if len(mono_stack) > 1:\n",
    "            for i in range(1, len(mono_stack)):\n",
    "                nodes_array[mono_stack[i - 1]].next = nodes_array[mono_stack[i]]\n",
    "        else:\n",
    "            nodes_array[mono_stack[0]].next = None\n",
    "        return nodes_array[mono_stack[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = ListNode()\n",
    "        pre.next = head\n",
    "        stack = []\n",
    "        cur = head\n",
    "        while cur:\n",
    "            while stack and cur.val > stack[-1][1].val:\n",
    "                node = stack.pop()\n",
    "                node[0].next = cur\n",
    "                pre = node[0]\n",
    "            stack.append((pre,cur))\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        return stack[0][1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return head\n",
    "        lis = []\n",
    "        p = head\n",
    "        while p:\n",
    "            lis.append(p.val)\n",
    "            p = p.next\n",
    "        del_set = set()\n",
    "        for i in range(len(lis) - 2, -1, -1):\n",
    "            if lis[i] < lis[i + 1]:\n",
    "                lis[i] = lis[i + 1]\n",
    "                del_set.add(i)\n",
    "        empty_head = ListNode(0, head)\n",
    "        p = empty_head\n",
    "        i = -1\n",
    "        while p.next:\n",
    "            if (i + 1) in del_set:\n",
    "                p.next = p.next.next\n",
    "                i += 1\n",
    "            else:\n",
    "                p = p.next\n",
    "                i += 1\n",
    "        return empty_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        answer = None\n",
    "\n",
    "        if head != None:\n",
    "            nums = []\n",
    "            node = head\n",
    "            while node != None:\n",
    "                nums.append(node.val)\n",
    "                node = node.next\n",
    "            \n",
    "            nums_size = len(nums)\n",
    "            array = [-1 for i in range(0, nums_size)]\n",
    "            stack = []\n",
    "            for x in range(0, nums_size):\n",
    "                while stack and nums[stack[-1]] < nums[x]:\n",
    "                    array[stack.pop(-1)] = x\n",
    "                stack.append(x)\n",
    "            \n",
    "            _list = []\n",
    "            node = head\n",
    "            for x in array:\n",
    "                if x == -1:\n",
    "                    _list.append(node)\n",
    "                node = node.next\n",
    "            \n",
    "            if _list:\n",
    "                last = None\n",
    "                while _list:\n",
    "                    node = _list.pop(-1)\n",
    "                    node.next = last\n",
    "                    last = node\n",
    "                answer = last\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        top = ListNode(100000, head)\n",
    "        cur, p = top, {}\n",
    "        while cur.next:\n",
    "            while cur.val < cur.next.val:\n",
    "                pre = p[cur]\n",
    "                pre.next = cur.next\n",
    "                cur = pre\n",
    "            p[cur.next] = cur\n",
    "            cur = cur.next\n",
    "        return top.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 用索引当作唯一key\n",
    "        lst = []\n",
    "        cur = head \n",
    "        rec = dict()\n",
    "        while cur:\n",
    "            rec[len(lst)] = cur \n",
    "            lst.append(cur.val)\n",
    "            cur = cur.next \n",
    "        n = len(lst)\n",
    "        remain = [True for _ in range(n)]\n",
    "        tMax = lst[-1]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            tMax = max(tMax,lst[i])\n",
    "            if tMax > lst[i]:\n",
    "                remain[i] = False \n",
    "        dummy = ListNode()\n",
    "        cur = dummy\n",
    "        for i in range(n):\n",
    "            if remain[i]:\n",
    "                cur.next = rec[i]\n",
    "                cur = cur.next \n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(10000000, head)\n",
    "        head.pre = dummy\n",
    "        pre, now = head, head.next\n",
    "        now.pre = pre\n",
    "        while now:\n",
    "            nxt = now.next\n",
    "            while now.val > pre.val:\n",
    "                pre = pre.pre\n",
    "            pre.next = now\n",
    "            now.pre = pre\n",
    "            pre, now = now, nxt\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack = []\n",
    "        while head:\n",
    "            while stack and head.val > stack[-1]:\n",
    "                stack.pop()\n",
    "            stack.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        sentinel = cur = ListNode()\n",
    "        for s in stack:\n",
    "            cur.next = ListNode(s)\n",
    "            cur = cur.next\n",
    "        return sentinel.next\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack = []\n",
    "        while head:\n",
    "            while stack and stack[-1] < head.val:\n",
    "                stack.pop()\n",
    "            stack.append(head.val)\n",
    "            head = head.next\n",
    "        dummy = ListNode()\n",
    "        start = dummy\n",
    "        for num in stack:\n",
    "            dummy.next = ListNode(num)\n",
    "            dummy = dummy.next\n",
    "        return start.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        temp=ListNode(0,head)\n",
    "        l=list()\n",
    "        while temp.next:\n",
    "            temp=temp.next\n",
    "            while l and l[-1]<temp.val:\n",
    "                l.pop()\n",
    "            l.append(temp.val)\n",
    "        temp=ListNode()\n",
    "        head=ListNode()\n",
    "        temp.next=head\n",
    "        for i in range(len(l)):\n",
    "            t=ListNode(l[i])\n",
    "            head.next=t\n",
    "            head=head.next\n",
    "        return temp.next.next\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = []\n",
    "        node = head\n",
    "        while node:\n",
    "            cur.append(node.val)\n",
    "            node = node.next\n",
    "        cur.reverse()\n",
    "        n = len(cur)\n",
    "        cnt = cur[0]\n",
    "        out = []\n",
    "        for i in range(n):\n",
    "            if cur[i] >= cnt:\n",
    "                out.append(cur[i])\n",
    "                cnt = cur[i]\n",
    "        out.reverse()\n",
    "        head_out = ListNode(out[0])\n",
    "        node = head_out\n",
    "        for i in range(1, len(out)):\n",
    "            new_node = ListNode(out[i])\n",
    "            node.next = new_node\n",
    "            node = node.next\n",
    "        return head_out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        arr=[]\n",
    "        p=head\n",
    "        while p:\n",
    "            arr.append(p.val)\n",
    "            p=p.next\n",
    "        n=len(arr)\n",
    "        s=[]\n",
    "        res=[n]*n\n",
    "        for i,x in enumerate(arr):\n",
    "            while s and arr[s[-1]]<x:\n",
    "                res[s.pop()]=i\n",
    "            s.append(i)\n",
    "        #print(res)\n",
    "        dummy=ListNode()\n",
    "        p=dummy\n",
    "        for i,x in enumerate(res):\n",
    "            if x==n:\n",
    "                p.next=ListNode(arr[i],None)\n",
    "                p=p.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        p=head\n",
    "        path=[]\n",
    "        cnt=0\n",
    "        while p:\n",
    "            path.append(p.val)\n",
    "            cnt+=1\n",
    "            p=p.next\n",
    "        subs=[False for i in range(cnt)]\n",
    "        s=[]\n",
    "        for i in range(cnt):\n",
    "            while len(s)>0 and path[i]>path[s[-1]]:\n",
    "                subs[s[-1]]=True\n",
    "                s.pop()\n",
    "            s.append(i)\n",
    "        L=ListNode(0)\n",
    "        L.next=None\n",
    "        q=L\n",
    "        for i in range(cnt):\n",
    "            if subs[i]==False:\n",
    "               q.next=ListNode(path[i])\n",
    "               q=q.next\n",
    "        return L.next\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        import heapq\n",
    "        H=[]\n",
    "        pos=0\n",
    "        while head:\n",
    "            a=head.val\n",
    "            pos+=1\n",
    "            heapq.heappush(H,(-a,pos))\n",
    "            head=head.next\n",
    "        J=[]\n",
    "        cur=0\n",
    "        while H:           \n",
    "            u=heapq.heappop(H)\n",
    "            ind=u[1]\n",
    "            if ind>cur:\n",
    "                J.append(-u[0])\n",
    "                cur=ind\n",
    "        def createhead(lst):\n",
    "            first=lst.pop(0)\n",
    "            head = ListNode(first)\n",
    "            tail = head\n",
    "            for i in range(len(lst)):\n",
    "                pt = ListNode(lst[i])\n",
    "                tail.next = pt\n",
    "                tail = pt\n",
    "            return head\n",
    "        fin=createhead(J)\n",
    "        return fin\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        self.nums = []\n",
    "        while cur:\n",
    "            self.nums.append(cur.val)\n",
    "            cur = cur.next\n",
    "        N = len(self.nums)\n",
    "        cur_max = self.nums[-1]\n",
    "        res = [N-1]\n",
    "        for i in range(N-2, -1, -1):\n",
    "            if self.nums[i]>=cur_max:\n",
    "                res.append(i)\n",
    "                cur_max = self.nums[i]\n",
    "        res = set(res)\n",
    "        # print(res)\n",
    "        i=0\n",
    "        cur = head\n",
    "        y = ListNode(-1)\n",
    "        yy = y\n",
    "        while cur:\n",
    "            if i in res:\n",
    "                y.next = ListNode(val=cur.val)\n",
    "                y = y.next\n",
    "            cur = cur.next\n",
    "            i+=1\n",
    "        # y.next = None\n",
    "        return yy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: ListNode) -> ListNode:\n",
    "        temp = head\n",
    "        res = []\n",
    "        while temp:\n",
    "            res.append(temp.val)\n",
    "            temp = temp.next\n",
    "\n",
    "        right = [-1] * len(res)\n",
    "        stack = []\n",
    "        for i, val in enumerate(res):\n",
    "            while stack and stack[-1][0] < val:\n",
    "                right[stack.pop()[1]] = i\n",
    "            stack.append((val, i))\n",
    "\n",
    "        temp = ans = ListNode()\n",
    "        for i, val in enumerate(right):\n",
    "            if val < 0:\n",
    "                temp.next = ListNode(val=res[i])\n",
    "                temp = temp.next\n",
    "\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        #print(head)\n",
    "        arr = []\n",
    "        temp = head\n",
    "        while(temp):\n",
    "            arr.append(temp.val)\n",
    "            temp = temp.next\n",
    "        n = len(arr)\n",
    "        stack = []\n",
    "        ans = [-1]*n\n",
    "        for i in range(n):\n",
    "            if stack == []:\n",
    "                stack.append([arr[i],i])\n",
    "            else:\n",
    "                while(stack!= [] and stack[-1][0] < arr[i]):\n",
    "                    a = stack.pop()\n",
    "                    ans[a[1]] = 1\n",
    "                stack.append([arr[i],i])\n",
    "        #print(ans)\n",
    "        res = ListNode(0)\n",
    "        temp = res\n",
    "        temp.next = ListNode(0)\n",
    "        for i in range(n):\n",
    "            if ans[i] == -1:\n",
    "                temp.next = ListNode(arr[i])\n",
    "                temp = temp.next\n",
    "                #print(temp)\n",
    "        temp.next = None\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        arr = []\n",
    "        node = head\n",
    "        while node:\n",
    "            arr.append(node.val)\n",
    "            node = node.next\n",
    "        \n",
    "        # print(arr)\n",
    "        max_map = {}\n",
    "        max_num = -1\n",
    "        for i in range(len(arr)-1, -1, -1):\n",
    "            max_num = max(max_num, arr[i])\n",
    "            max_map[i] = max_num\n",
    "        # print(max_map)\n",
    "        new_list = []\n",
    "        for k, num in enumerate(arr):\n",
    "            if k < len(arr) - 1:\n",
    "                if num >= max_map[k+1]:\n",
    "                    new_list.append(num)\n",
    "            else:\n",
    "                new_list.append(num)\n",
    "        # print(new_list)\n",
    "        head = ListNode(val=new_list[0])\n",
    "        node = head\n",
    "        t = 0\n",
    "        for t in range(1, len(new_list)):\n",
    "            node.next = ListNode(val=new_list[t])\n",
    "            node = node.next\n",
    "            \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = head = self.reverseNodes(head)\n",
    "        \n",
    "        while pre.next:\n",
    "            if pre.val > pre.next.val:\n",
    "                pre.next = pre.next.next\n",
    "            else:\n",
    "                pre = pre.next\n",
    "\n",
    "        return self.reverseNodes(head)\n",
    "        \n",
    "    def reverseNodes(self, head):\n",
    "        dummy = ListNode()\n",
    "        pre = head\n",
    "        while pre:\n",
    "            node = ListNode(pre.val)\n",
    "            node.next = dummy.next\n",
    "            dummy.next = node\n",
    "            pre = pre.next\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        class reversenode:\n",
    "            def __init__(self,val=0,pre=None,node=None):\n",
    "                self.node=node\n",
    "                self.val=val\n",
    "                self.pre=pre\n",
    "        node=head.next\n",
    "        pre=head\n",
    "        nownode=None\n",
    "        while node!=None:\n",
    "            pre1=reversenode(pre.val,nownode,pre)\n",
    "            nownode=reversenode(node.val,pre1,node)\n",
    "            pre=node\n",
    "            node=node.next\n",
    "        root=nownode\n",
    "        nowmax=root.val\n",
    "        node=root.pre\n",
    "        while node.pre!=None:\n",
    "            if node.val>nowmax:\n",
    "                nowmax=node.val\n",
    "            elif node.val<nowmax:\n",
    "                node.pre.node.next=node.node.next\n",
    "            node=node.pre\n",
    "        if node.val<nowmax:\n",
    "            head=node.node.next\n",
    "        return head\n",
    "                \n",
    "        \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        arr = []\n",
    "        p = head\n",
    "        while p:\n",
    "            arr.append(p.val)\n",
    "            p = p.next\n",
    "        dummy = ListNode(-1)\n",
    "        pq = []\n",
    "        for i,e in enumerate(arr):\n",
    "            heappush(pq,[-e,i])\n",
    "        ans = []\n",
    "        curIndex = -1\n",
    "        tmp = []\n",
    "        while len(pq)!=0:\n",
    "            e,i = heappop(pq)\n",
    "            e = -e\n",
    "            if curIndex>=i:\n",
    "                continue\n",
    "            else:\n",
    "                tmp.append([i,e])\n",
    "                curIndex = i\n",
    "        tmp.sort(key = lambda x:x[0])\n",
    "        p = dummy\n",
    "        for i,e in tmp:\n",
    "            p.next = ListNode(e)\n",
    "            p = p.next\n",
    "        return dummy.next\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = self.reverseNodes(head)\n",
    "        \n",
    "        dummy1 = ListNode(-1)\n",
    "        pre = dummy1\n",
    "        cur = dummy.next\n",
    "        while cur:\n",
    "            if cur.val >= dummy1.val:\n",
    "                dummy1.next = ListNode(cur.val)\n",
    "                dummy1 = dummy1.next\n",
    "            cur = cur.next\n",
    "\n",
    "        res = self.reverseNodes(pre.next)\n",
    "        return res.next\n",
    "        \n",
    "    def reverseNodes(self, head):\n",
    "        dummy = ListNode()\n",
    "        pre = head\n",
    "        while pre:\n",
    "            node = ListNode(pre.val)\n",
    "            node.next = dummy.next\n",
    "            dummy.next = node\n",
    "            pre = pre.next\n",
    "        return dummy\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        node_list = []\n",
    "        d = defaultdict(deque)\n",
    "        idx = 0\n",
    "        while cur:\n",
    "            node_list.append(cur.val)\n",
    "            d[cur.val].append(idx)\n",
    "            cur = cur.next\n",
    "            idx += 1\n",
    "        \n",
    "        ans = sorted(d.items(), key=lambda x: -x[0])\n",
    "        # print(ans)\n",
    "        head = pre = ListNode(ans[0][0])\n",
    "        cur_idx = d[ans[0][0]].popleft()\n",
    "        for k, l in ans:\n",
    "            while l:\n",
    "                idx = l.popleft()\n",
    "                if idx > cur_idx:\n",
    "                    cur_idx = idx\n",
    "                    node = ListNode(k)\n",
    "                    pre.next = node\n",
    "                    pre = node\n",
    "        return head\n",
    "#         def get_max(l):\n",
    "#             if not l:\n",
    "#                 return None\n",
    "#             max_value = max(l)\n",
    "#             max_index = l.index(max_value)\n",
    "            \n",
    "#             node = ListNode(max_value)\n",
    "#             node.next = get_max(l[max_index+1:])\n",
    "#             return node\n",
    "        \n",
    "#         return get_max(node_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head.next:\n",
    "            return head\n",
    "        head.next = self.removeNodes(head.next)\n",
    "        return head if head.val >= head.next.val else head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next: return head\n",
    "        nextNode = self.removeNodes(head.next)\n",
    "        if nextNode.val > head.val: return nextNode\n",
    "        head.next = nextNode\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Python3 模拟\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        stack = [head]\n",
    "        head = head.next\n",
    "        while head:\n",
    "            while stack and stack[-1].val < head.val:\n",
    "                stack.pop()\n",
    "            stack.append(head)\n",
    "            head = head.next\n",
    "        phead = ListNode(0)\n",
    "        cur = phead\n",
    "        for i in stack:\n",
    "            cur.next = i\n",
    "            cur = i\n",
    "        return phead.next\n",
    "\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Python3 递归\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        node = self.removeNodes(head.next)\n",
    "        if node.val > head.val:\n",
    "            return node\n",
    "        head.next = node\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "    max_val = 0\n",
    "\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head == None:\n",
    "            return\n",
    "        head.next = self.removeNodes(head.next)\n",
    "        if head.val < self.max_val:\n",
    "            return head.next\n",
    "        else:\n",
    "            self.max_val = head.val\n",
    "            return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\r\n",
    "\r\n",
    "        # 递归法 删除所有小于右侧节点值的节点\r\n",
    "        # 递归遍历至链表尾部\r\n",
    "        # 回溯，判断current_node(head)与next_node之间值的大小\r\n",
    "        #   如果 current_node 小于 next_node, 则 return next_node，即删除current_node\r\n",
    "        #   如果 current_node 不小于 next_node，则 return current_node\r\n",
    "        def removeSmallerNode(head):\r\n",
    "            if head.next == None:\r\n",
    "                return head\r\n",
    "            next_node = removeSmallerNode(head.next)\r\n",
    "            if head.val < next_node.val:\r\n",
    "                return next_node\r\n",
    "            else:\r\n",
    "                head.next = next_node\r\n",
    "                return head\r\n",
    "        \r\n",
    "        return removeSmallerNode(head)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head.next is None: return head  # 输入保证链表不为空\n",
    "        node = self.removeNodes(head.next)  # 返回的链表头一定是最大的\n",
    "        if node.val > head.val: return node  # 删除 head\n",
    "        head.next = node  # 不删除 head\n",
    "        return head\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
